This application claims priority under 35 U.S.C. xc2xa7xc2xa7119 and/or 365 to Application No. 0003446-2 filed in Sweden on Sep. 27, 2000; the entire content of which is hereby incorporated by reference.
The present invention relates to the field of pipelined microprocessors and particularly to a pipelined microprocessor capable of handling instruction irregularities such as exceptions, interrupts and branch mispredictions and to a method of handling instruction irregularities in a pipelined microprocessor.
So called pipelined processors have been developed to speed up the processing speed of computer processors and to improve or increase the instruction flow through a microprocessor. A pipelined processor includes a plurality of independently operating stages. When a first instruction has been handled in one of the pipeline stages, it is moved on to the next stage whereas a subsequent instruction is received in the stage that a preceding instruction just left. Generally several instructions are processed simultaneously in the pipeline since each stage may bold an instruction. So called super-scalar processors are also known which comprise multiple pipelines processing instructions simultaneously when adjacent instructions have no data dependencies between them. A super-scalar processor commits more than one instruction per cycle. Through the provision of out-of-order processors an even higher degree of parallellism and a higher performance can be provided for. An out-of-order processor includes multiple parallell stages/units in which instructions are processed in parallell in any efficient order taking advantage of parallell processing. Out-of-order processing is much more complex than conventional processing among others due to the need of state recovery following unpredicted changes in the instruction flow.
Microprocessors may implement the technique of overlapping a fetching stage, a decoding stage, an execution stage and possibly a write back stage. In a so called deeply pipelined microprocessor each processing stage is divided into sub-stages to still further increase the performance.
Generally state recovery mechanisms are introduced in order to provide for state recovery following an exception, an interrupt or a branch misprediction which in the present application are gathered under a common concept of instruction irregularity.
Exceptions are generally unexpected events associated with the instructions such as page fault and memory accesses, data break point traps or divided-by-zero conditions.
Interrupts are events occurring from outside of the processor that may be initiated for example by the devices coupled to the same buses or processors.
A branch instruction is an instruction that expressly changes the flow of program. Branch instructions may be conditional or unconditional. An unconditional branch instruction is always taken whereas a conditional branch instruction either is taken or not taken depending on the results of the condition expressed within the instruction. Conditional branch instructions within an instruction stream generally prevent the instruction fetching stage from fetching subsequent instructions until the branch condition is fully resolved.
In a pipelined microprocessor a conditional branch instruction will not be fully resolved until it reaches an instruction execution stage close to the end of the pipeline. The instruction fetching stage will then stall because the unresolved branch condition prevents the instruction fetching stage from knowing which instructions to fetch next. This is clearly disadvantageous.
Therefore it is known to implement various branch prediction mechanisms to predict the outcome of a branch instruction. The instruction fetching stage then uses the branch predictions to fetch subsequent instructions. Therethrough it is not necessary to wait until the branch instruction has been fully resolved.
If a branch prediction has made a correct prediction, the processing of instructions is not affected. If however the mechanism has mispredicted the branch, the instruction pipeline has to be flushed and execution is to be restarted at the corrected address. It is therefore desirable to detect and correct a branch misprediction as early as possible, particularly for deeply pipelined processors where a long pipeline needs to be flushed each time a misprediction is made.
U.S. Pat. No. 5,812,839 suggests a solution to this problem through using a four stage branch instruction resolution system. A first stage predicts the existence and outcome of branch instructions within an instruction stream such that an instruction fetching stage continually can fetch instructions. The second stage decodes all the instructions fetched. If the decode stage determines that a supposed branch instruction predicted by the first stage is not actually a branch instruction, the decode stage flushes the pipeline and restarts the processor at a corrected address. The decode stage verifies all branch predictions made by the branch prediction stage. The decode stage makes branch predictions for branches not predicted by the branch prediction stage. A third stage executes the branch instructions to determine a final branch outcome and a final branch target address. The branch execution stage compares the final branch outcome and the final branch target address with the prediction to determine if the processor has to flush the front-end of the microprocessor pipeline and restart again at a corrected address. The final branch resolution stage retires all branch instructions ensuring that any instructions fetched after a mispredicted branch are not committed into permanent state. It is clearly disadvantageous that the whole front-end needs to be flushed if there has been a misprediction.
It is also a serious drawback in all known pipelined microprocessors, implementing speculative prediction, that at several different locations and stages a part of the information has to be disposed of. All data belonging to the instructions after a mispredicted branch need to be flushed. The more steps the pipeline contains, the more serious the problem will be since larger memories and longer queues have to be searched in order to find the data that is to be disposed of. This of course seriously affects the performance.
What is needed is therefore a pipelined microprocessor capable of handling instruction irregularities, such as one or more of exceptions, interrupts and branch mispredictions, in a more efficient manner compared to hitherto known pipelined processors. Particularly a pipelined microprocessor is needed through which instruction irregularities can be handled in an efficient manner with a minimum of performance reduction, compared to the situation when there is no instruction irregularity. Further a pipelined microprocessor is needed through which invalid instructions associated with an instruction irregularity can be handled as efficiently as possible. Particularly a pipelined processor is needed through which branch mispredictions to a minimum extent affect execution and through which no flushing is needed in those execution units that are not handling a branch misprediction.
Particularly a pipelined microprocessor that implements speculative execution is needed, through which mispredicted branch instructions do not require flushing of the front-end with a corresponding restart when a mispredicted branch instruction is detected.
In addition to a pipelined microprocessor, a method of handling instruction irregularities, and through which one or more above mentioned objects can be fulfilled, is also needed.
In the present application the concept functional stage is introduced to indicate that the functionality referred to may be provided in one or more separate xe2x80x9csubxe2x80x9d-stages providing the same functionality, or more than one functionality may be provided in a combined stage. As an example the xe2x80x9cconventionalxe2x80x9d decoding stage could be provided in more than one stage; this is of course applicable to any one of the functional stages. Alternatively two or more functional stages could be provided in a combined stage etc. When referring to a stage in the present application is generally meant a functional stage. The invention therefore provides a microprocessor for processing instructions, comprising at least one pipeline which comprises; an instruction fetching functional stage; an instruction decoding functional stage; an execution functional stage, comprising one or more execution units; and a commit functional stage comprising or being associated with a reorder buffer.
Means are also provided for detecting instruction irregularities e.g. at the execution functional stage (or at the commit functional stage), such that when an instruction irregularity is detected, an irregularity indication is generated to initiate a flush mode and to indicate the provision of a flush instruction. In an advantageous implementation the irregularity indication comprises an irregularity indication signal. However, also other ways of providing an indication are of course possible.
In one implementation the execution unit that handles the instruction irregularity generates the irregularity indication (signal). The flush instruction may particularly be provided from the instruction fetching functional stage.
The irregularity indication signal puts at least the execution unit handling the irregularity in the execution functional stage, into flush mode. In advantageous implementations it also puts the decoding functional stage in flush mode. Further, the instruction that caused the irregularity may by well-known measures be marked as causing the irregularity. The commit functional stage is then put into flush mode when said marked instruction is committed. Alternatively the irregularity indication (signal) puts at least the commit functional stage in flush mode. It may then be generated in the commit functional stage. Then, preferably, but not necessary, also all execution units of the execution functional stage are set in flush mode.
All instructions that are processed by a functional stage or a unit in flush mode are provided with a cancel marking. Particularly, all instructions processed in the decoding functional stage, and in the execution unit handling the instruction irregularity, are provided with a cancel marking. However, instructions processed in other execution units are not marked at least unless the irregularity is detected at the commit stage, An execution unit handling an instruction irregularity is in the following denoted a specific execution unit, whereas a dedicated execution unit is taken to mean an execution unit taking care of branch instructions, as will be further described below.
If an instruction has not been canceled marked in earlier (functional) stages or units of the pipelined microprocessor, the instruction is provided with a cancel marking when processed by the commit stage in flush mode. It is then to be noted that all instructions handled in the decoding functional stage, or in the specific execution unit handling the instruction irregularity, are canceled marked in that stage or unit during flush mode.
The flush instruction should at least be provided to the specific execution unit handling the instruction irregularity. In implementations in which the decoding stage is set in flush mode, the flush instruction is preferably also provided to the decoding stage, i.e. it is input to the pipeline before, or at, the decoding functional stage. The flush instruction is otherwise processed in an ordinary manner throughout the stages. However, upon arrival at functional stages or units in flush mode the flush instruction will reset the flush mode for that stage or unit. Especially, the flush instruction will reset the specific execution unit handling the instruction irregularity.
It is also to be noted that during flush mode particularly no command is issued to external units from the specific execution unit handling an instruction irregularity.
The pipelined microprocessor is particularly a deeply pipelined processor and in one particular implementation it is capable of handling instruction irregularities, e.g. exceptions and/or interrupts. Even more particularly it is capable of handling instruction irregularities comprising branch instructions. The inventive concept thus covers microprocessors able to handle one or more of branch (mis)predictions, exceptions and interrupts in a most efficient way.
Particularly the microprocessor is a speculative out-of-order processor implementing branch prediction, e.g. predicting whether a conditional branch or jump is to be taken or not. In a specific embodiment there are (one or more) dedicated execution units that are used for handling branch or jump instructions. These units may of course also handle other types of instructions in addition to branch instructions. However, the main thing is that all branch instructions are checked for instruction irregularity in the same order as they were provided to the decoding functional stage. One way to accomplish this is to provide a reservation functional stage, with a reservation unit, which precedes the dedicated execution unit and in which the branch instructions are handled in order. The concept dedicated execution unit is here merely introduced for reasons of clarity and it means an execution unit to which branch instructions may be directed. This is not introduced for limitative purposes; branch instructions may be directed to one or more execution units, dedicated (here) execution units may handle other instructions as well.
A conditional branch or jump is particularly predicted in the instruction fetching functional stage. To establish if the prediction was correct or not, information about the final outcome of the prediction is particularly provided from the execution unit handling the predicted branch instruction to detecting means. Particularly, said (dedicated) execution unit comprises the detecting means. Alternatively, said means may be located outside the pipeline, notifying the execution unit of an instruction irregularity. The detecting means may also be provided in, or in association with, the fetching functional stage.
If the prediction was correct, a response with information about it is returned to said dedicated execution unit from the detecting means. If the prediction was incorrect, a response that will generate an irregularity indication (signal) and a flush instruction is returned from the detecting means to said dedicated (specific) execution unit.
In an alternative implementation no response is provided if the prediction was incorrect, but an irregularity indication (signal) is generated. The irregularity indication (signal) is, according to one embodiment, sent from the execution unit handling the mispredicted branch instruction. Alternatively it is sent from the detecting means wherever they are located, as discussed above. In a particular implementation the irregularity indication comprises a 1-bit signal. The flush instruction is preferably generated in the decoding functional stage, but it may be generated elsewhere, e.g. in the fetching functional stage or externally of the pipeline.
In a particular implementation the detecting means are provided in, or in association with, the commit functional stage. In addition to the pipelined microprocessor, discussed above, the invention also provides a method for handling instruction irregularities, e.g. exceptions, interrupts, mispredicted branch instructions, in a microprocessor, comprising at least one pipeline which comprises an instruction fetching functional stage, an instruction decoding functional stage, an execution functional stage and a commit functional stage.
The method comprises the steps of; detecting an instruction irregularity by detecting means; providing an irregularity indication; putting at least the (specific) execution unit handling the instruction irregularity into flush mode; generating a flush instruction; inputting the flush instruction to the pipeline; cancel marking instructions during the flush mode; directing the flush instruction to said specific execution unit; and resetting the flush mode in each functional stage or unit in flush mode upon reception or handling of the flush instruction. Particularly the method includes the step of; marking the instruction causing the irregularity when detecting the instruction irregularity.
Particularly the steps of detecting an instruction irregularity comprises; predicting if an instruction might cause an irregularity; attaching the result of the predicted outcome to said instruction so that the result follows the instruction through the pipeline; processing of the instruction in an execution unit to evaluate if the instruction actually caused an irregularity; detecting if the prediction was correct; if the prediction was correct the processing is continued as normal, otherwise an irregularity indication (signal) is generated to indicate the provision of the flush instruction and to initiate the flush mode.
Particularly, it is advantageous if the specific execution unit that handles the instruction irregularity also generates the irregularity indication (signal).
Particularly, the irregularity indication (signal) puts the decoding functional stage, and the execution unit handling the irregularity in the execution functional stage, into flush mode Further, the instruction that caused the irregularity is by well-known measures marked as causing the irregularity. The commit functional stage is then put into flush mode when said marked instruction is committed.
Particularly, all instructions that are processed by a stage or unit in flush mode are provided with a cancel marking Particularly, all instructions processed in the decoding functional stage, and in the execution unit handling the instruction irregularity, are provided with a cancel marking. If an instruction has not been canceled marked in earlier functional stages or units of the pipelined microprocessor, the instruction is provided with a cancel marking when processed by the commit functional stage in flush mode. Alternatively the method comprises the step of detecting an instruction irregularity at the commit functional stage. An irregularity indication is then generated which is used to set at least the commit functional stage in flush mode. Preferably it is also used to set the entire execution functional stage in flush mode.
According to the invention may an indication, e.g. a cancel marking, be set as an irregularity is detected, and fetching of the correct code, or instruction, is immediately initiated from the appropriate location or xe2x80x9csourcexe2x80x9d. This is clearly advantageous e.g. as far as the performance is concerned. It is not necessary to explicitely and physically remove all instructions from e.g. the reorder buffer, reservation stage etc. at the same time, particularly between the execution and commit stages and between the fetching and issuance stages. The flush mode could even be implemented as a step of going through instructions without executing them, i.e. ignoring them. According to the invention it is not necessary to quickly send the flush indication through the whole pipeline. Furthermore it is not necessary to search for all instructions in order to cancel mark them. Instead a xe2x80x9cmodexe2x80x9d is set which cancels all passing instructions until the flush instruction arrives.
Particularly flush mode means that, all incoming or passing instructions are ignored. The first indication that flash mode should be set, e.g. the first cancel marking, indicates that the flush mode is to be set (ignoring instructions). Subsequent cancel markings has a different meaning, i.e. simply that the instructions should be ignored. In one implementation cancel marking is not required when a unit/stage is in flush mode since then this will be done by the commit stage.
It is an advantage of the invention that the front-end of the pipeline does not need to be flushed and that execution can be proceeded almost unaffected when for example a mispredicted branch instruction is detected. It is also an advantage that there is no need to search for every particular location in queues, storing means etc. to just flush the data that becomes invalid due to the instruction irregularity. If a branch instruction is mispredicted there is actually no conventional flushing at all, but the instructions can be said to be committed as canceled marked, i.e. such instructions do not cause any further processing. As soon as an instruction irregularity or particularly a mispredicted branch instruction is detected, the correct instruction is input to the instruction fetching functional stage directly after the flush instruction and all the following instructions are processed in a normal manner. Consequently, all the following instructions will be carried out orderly once the flush mode has been reset by the flush instruction. It is an advantage of the invention that restart of the fetching of instructions is possible directly when an instruction irregularity has been detected e.g. in the execution stage.